#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <fcntl.h>
#include <limits.h>

#define BLOCK_SIZE 256*1024

// Una forma de implementar block sorting, es con un 'suffix array',
// es decir con un array de sufijos que en realidad son las 'rotaciones' de
// block sorting 

// En este caso, el puntero de indicies apunta al sufijo y el +1 es el indice
// del tamaño final de bloque.

long length;
unsigned char buffer[BLOCK_SIZE];
int indices[BLOCK_SIZE];

/*
 * Funcion de comparación que ordena el array de suffijos.
 * 
 * Recibe puntero al array de indicies que se usan para obtener y comparar los
 * sufijos.
 */
int blocksorting_cmp( const unsigned int *i1, const unsigned int *i2 ) {
    unsigned int l1 = (unsigned int) ( length - *i1 );
    unsigned int l2 = (unsigned int) ( length - *i2 );
    // priorizo el uso de registros en lugar de stack para estas operaciones
    // aunque el compilador podria usarlos de cualquier manera
    register unsigned char *str1 = buffer + *i1, *str2 = buffer + *i2;
    register int result = 0, len = 0;    
    
    // Uso una implementacion mejor que memcmp.
    // memcmp puede tener comportamientos distintos (signed/unsigned) y
    // implementaciones poco optimizadas
    
    // result = memcmp(buffer + *i1, buffer + *i2, l1 < l2 ? l1 : l2 );
  
    len = length;
    result = 0;
    while (len-- && result == 0) {
      if (str2 - buffer >= length) {
        str2 = buffer;
      }
      if (str1 - buffer >= length) {
        str1 = buffer;
      }
      result = *str1++ - (int)*str2++;
    }
    
    return result;
};


int main( int argc, char **argv ) {   
  int i, j;
  
  while (1) {
    length = fread( (char *) buffer, 1, BLOCK_SIZE, stdin );
    if ( length == 0 )
        break;
    fprintf( stderr, "Blocksorting in %ld bytes\n", length );
        // Necesito la longitud del bloque para hacer la transformacion inversa
    fwrite( (char *) &length, 1, sizeof( long ), stdout );

    /*
     * Ordenar el array de sufijos se hace simplemente teniendo punteros
     * a cada elemento del bloque (sufijo) y llamando a la funcion qsort()
     * que ordena los punteros usando una funcion de qsort especial.
     * 
     */

    for ( i = 0 ; i < length ; i++ ) {
      indices[ i ] = i;
    }

    qsort(  
      indices, 
      (int)( length ), 
      sizeof( int ), 
      ( int (*)(const void *, const void *) ) blocksorting_cmp 
    );

    /*
     * Finalmente escribo la columna L consiste en los caracteres anteriores
     * a los sufijos. En el caso de del primer string (indice = 0), su prefijo
     * es el ultimo caracter del bloque, y emito la posición del primer 
     * caracter como el caracter imaginario para poder hacer la transformación 
     * inversa.
     */
    
         if ( 0 ) {
            for ( i = 0 ; i < length ; i++ ) {
                fprintf( stderr, "%d : ", i );
                unsigned char prefix;
                if ( indices[ i ] == 0 )
                    prefix = (unsigned char) buffer[ length - 1 ];
                else
                    prefix = (unsigned char) buffer[ indices[ i ] - 1 ];
                if ( isprint( prefix ) )
                    fprintf( stderr, "%c", prefix );
                else
                    fprintf( stderr, "<%d>", prefix );
                fprintf( stderr, ": " );
                int stop = (int)( length - indices[ i ] );
                if ( stop > 30 )
                    stop = 30;
                for ( j = 0 ; j < stop ; j++ ) {
                    if ( isprint( buffer[ indices[ i ] + j ] ) )
                        fprintf( stderr, "%c", buffer[ indices[ i ] + j ] );
                    else
                        fprintf( stderr, "<%d>", buffer[ indices[ i ] + j ] );
                }
                fprintf( stderr, "\n" );
            }
        }   
    
      long first;
      for ( i = 0 ; i < length ; i++ ) {
          if ( indices[ i ] == 0 )
              first = i;
          if ( indices[ i ] == 0 ) {
              // mando el ultimo caracter del bloque
              fputc( buffer[ length - 1 ], stdout );
          } else
              fputc( buffer[ indices[ i ] - 1 ], stdout );
      }
      fprintf( stderr,
               "I = %ld\n",
               first);
      fwrite( (char *) &first, 1, sizeof( long ), stdout );
    }
    return 0;
}